export const sortQuickly = (array: number[]) => {
  let result = array;

  if (array.length > 1) {
    const base = array[0];

    let head = 1;
    let end = array.length - 1;
    
    while (head < end) {
      if (array[head] > base && array[end] < base) {
        const temp = array[head];
        array[head] = array[end];
        array[end] = temp;
      }
      if (array[head] <= base) {
        head++;
      }
      if (array[end] >= base) {
        end--;
      }
    }

    let iChange = array[end] > array[head] ? head : end;

    if (array[iChange] > array[0]) {
      iChange = iChange - 1;
    }

    if (iChange > 0) {
      const temp = array[iChange];
      array[iChange] = array[0];
      array[0] = temp;
    } else {
      iChange = 1;
    }

    let left = sortQuickly(array.slice(0, iChange));
    let right = sortQuickly(array.slice(iChange));
    result = [...left, ...right];
  }

  return result;
};
